1. Field of the Invention
This invention relates generally to arbitration of competing requests between a plurality of requesters in electronic systems, especially computer systems, and more specifically to hierarchical arbitration mechanisms required to arbitrate competing requests.
2. Description of the Related Art
In a complex computer system multiple processing units may share certain hardware resources, such as a data bus. Arbitration logic is used to arbitrate between competing requests from a number of separate requesters in the shared hardware resource. Arbitration logic can be implemented in a single central arbiter, or it can be implemented in a hierarchical or distributed arbiter. There are problems with each of these types of methods of arbitration.
A central arbiter 100 is shown in prior art FIG. 1, having requestors J0-J4, referenced as 102A-102E, respectively. Requestors J0-J4 is coupled to selection logic 112 by busses 104A-104E, respectively. Central arbiter 100 outputs a winning request on a signaling bus 114. One common problem with a central arbiter, such as central arbiter 100, as shown in FIG. 1, occurs when there are large numbers of requestors (only five, J0-J4, are shown, for simplicity in FIG. 1), or when the requestors are spread out physically. Central arbiters, such as central arbiter 100, require complex wiring. For example, requesters J0-J4 drive busses 104A-104E. Each bus 104A-104E typically comprises many wires, e.g., 64 wires. Busses 104A-104E all funnel into selection logic 112; a large number of wide busses (e.g. 64 bit busses) funneling into selection logic 112 causes wiring congestion problems. Because of physical distances busses 104A-104E must travel, additional time may be required for signal propagation, delaying each request. A control logic 110 provides control for selection logic 112 and, for example, may implement a round robin ordering or a first in, first out, ordering selection of requests.
To avoid the wiring congestion and wire length difficulties involved with a central arbiter, a hierarchical arbiter is often used when many requestors need to be arbitrated, especially when the requestors are physically widely separated. Several problems exist with prior art hierarchical arbiters. One common problem with a hierarchical arbiter occurs when requests need to be arbitrated in multiple levels of arbitration mechanisms. If requestors are not equally prolific (a more prolific requestor sends its requests to an arbitration mechanism more frequently than a non prolific requestor) in their requests, then a less prolific requestor may have to wait a considerable time before a request from the less prolific requestor is selected as a winning request. Requests from low level requestors are only infrequently chosen as the final winning request. A lower level requestor's requests must pass through more levels of arbitration in a hierarchical arbiter than a higher level requestor.
FIG. 2 illustrates an exemplary prior art hierarchical arbiter 200 to further explain inherent problems in prior art hierarchical arbiters. Hierarchical arbiter 200 comprises arbitration mechanisms 210A, 210B, 210C, and 210D, generically called arbitration mechanisms 210, with the appended letter used to denote particular instantiations of arbitration mechanism 210. Hereinafter, reference numerated items having an alphabetic character appended are particular instantiations of a generic item.
Arbitration mechanism 210A is a lowest level arbitration mechanism, (i.e. arbitration mechanism furthest away from a final stage of arbitration). Arbitration mechanisms 210B and 210C are higher level mechanisms, (i.e. arbitration mechanisms closer to the final stage of arbitration). Arbitration mechanism 210D is the highest level arbitration mechanism (i.e. the arbitration mechanism wherein the last stage of arbitration mechanism occurs).
Arbitration mechanism 210A arbitrates competing requests originating from requesters L0, L1 and L2. Requestors L0-L2 sends requests to a queue 204A. Requestors L0, L1, L2 each inform control logic 208A when they are driving valid requests, using additional signaling couplings (not shown). Requests from requesters L0-L2 are processed, under control of control logic 208A, within queue 204A on a round robin basis and the winning request is forwarded to higher level arbitration mechanism 210B on bus 214A. In some arbitration mechanisms 210, a FIFO (First In First Out) process is implemented instead of a round robin mechanism. For purposes of explanation, a round robin ordering will be used hereafter for arbitration mechanisms 210.
Arbitration mechanism 210B arbitrates competing requests from requesters L3, L4, and arbitration mechanism 210A. Arbitration mechanism 210A appears as a requester to arbitration mechanism 210B; however arbitration mechanism 210A is a nonprimitive requestor, since arbitration mechanism 210 arbitrates among several requestors. “Requestor” denotes a primitive requester, as opposed to an arbitration mechanism such as arbitration mechanism 210A, which will be referred to as nonprimitive requestors. A primitive requester is referred to as a “separate requestor”, or simply a “requestor”. Requestors L3 and L4, and arbitration mechanism 210A send requests to a queue 204B. Requests from requestors L3, L4, and arbitration mechanism 210A are processed within queue 204B on a round robin basis under control of a control logic 208B and the winning request is forwarded to arbitration mechanism 210D on a bus 214B. Requests sent on bus 214A are selected only ⅓ of the time (assuming that L3, L4, and arbitration mechanism 210A each always has an active request for arbitration mechanism 210B. If requestors L0, L1, and L2 are all prolific, L0, L1, and L2 each therefore win ⅓ of requests sent on bus 214A, and therefore only ⅓*⅓ or 1/9 of winning requests sent on bus 214B. Arbitration mechanism 210B appears as a nonprimitive requestor to arbitration mechanism 210D.
Arbitration mechanism 210C arbitrates requests originating from four competing requesters L5, L6, L7, and L8. Requestors L5-L8 sends requests to a queue 204C. Requests from requesters L5-L8 are processed, under control from control logic 208C, within queue 204C, on a round robin basis, and the winning request is forwarded to arbitration mechanism 210D on a bus 214C. Arbitration mechanism 210C appears as a nonprimitive requester to arbitration mechanism 210D.
Arbitration mechanism 210D arbitrates requests from four competing requesters: L9, L10, arbitration mechanism 210B, and arbitration mechanism 210C. Requests from requestors L9, L10, arbitration mechanism 210B, and arbitration mechanism 210C are processed, under control by a control logic 208D, within queue 204D on a round robin basis, and the winning request is output on a bus 214D. Bus 214D is further coupled to a request handler (not shown). The request handler can be different in different electronic systems. For example, in a first electronic system, the requests are computer executable instructions, and the request handler executes the winning requests. In another electronic system, the requests are for data movement, and the request handler moves data from a first location to a second location. This winning request is the winning request of the hierarchical arbiter.
The aggregate effect of hierarchical arbiter 200 can be very unfair, in particular, for requestors separated from the highest level arbitration mechanism (that is, the arbitration mechanism driving the winning request out of the hierarchical arbiter) by one or more intermediate level arbitration mechanisms. A hierarchical arbitration mechanism acts fair if, after a long period of time, and, if all requestors are submitting prolific requests, each requester has been chosen the winner of the fair hierarchical arbiter approximately the same number of times.
For example, if all requesters L0-L10 are prolific, each making constant requests, L9 and L10 would each get their request output on signal 214D (i.e., be the winning request) ¼ of the time (since queue 204D would always have active requests on each of its four inputs). Each of requestors L5, L6, L7, and L8 requesters would get a winning request only 1/16 of the time (four requesters each sharing one input to queue 204D, the one input to queue 204D itself is chosen only ¼ of the time). Similarly, each of requestors L3 and L4 would get a winning request 1/12 of the time. And, each of requesters L0, L1, L2 would get a winning request only 1/36 of the time. Since there are 11 requesters (L0-L10), a fair hierarchical arbiter would give each requester a winning request 1/11 of the time.
Therefore, there is a need for a method and apparatus that provides for a fair hierarchical arbiter.